Stack এর Operations (Push, Pop, Peek) গাইড ও নোট

Stack হল একটি linear data structure যা Last In, First Out (LIFO) (শেষে প্রবেশ, প্রথমে প্রস্থান) পদ্ধতির মাধ্যমে কাজ করে। অর্থাৎ, স্ট্যাকের শীর্ষে যে উপাদানটি প্রবেশ করে, সেটি প্রথমে বের করা হয়। স্ট্যাক সাধারণত তিনটি মৌলিক অপারেশন সমর্থন করে:

1. Push: একটি নতুন উপাদান স্ট্যাকে প্রবেশ করানো।
2. Pop: স্ট্যাকের শীর্ষ উপাদানটি বের করা (অথবা অপসারণ করা)।
3. Peek: স্ট্যাকের শীর্ষ উপাদানটি দেখতে পাওয়া, তবে এটি অপসারিত হয় না।

স্ট্যাকের এই তিনটি মৌলিক অপারেশন কিভাবে জাভায় বাস্তবায়িত করা যায়, তা দেখে নেওয়া যাক।

১. Stack Class in Java

জাভাতে, Stack ডেটা স্ট্রাকচারটি java.util.Stack ক্লাসের মাধ্যমে সরবরাহ করা হয়। তবে, Stack একটি অবলুপ্ত ক্লাস (legacy class) হিসেবে বিবেচিত, এবং নতুন অ্যাপ্লিকেশনগুলির জন্য Deque অথবা ArrayDeque ব্যবহারের পরামর্শ দেওয়া হয়, কারণ এগুলো স্ট্যাকের মত কার্যকারিতা সরবরাহ করে এবং আরও কার্যকরী।

তবে, Stack ক্লাসটি এখনও ব্যবহারযোগ্য এবং এতে push(), pop(), peek() সহ স্ট্যাক অপারেশনগুলো সহজে ব্যবহার করা যায়।

২. Stack Operations in Java

এখানে আমরা Stack ক্লাস ব্যবহার করে Push, Pop, এবং Peek অপারেশনগুলো দেখব।

উদাহরণ: Stack Operations (Push, Pop, Peek)

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        // Stack তৈরি করা
        Stack<Integer> stack = new Stack<>();

        // Push অপারেশন
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.push(40);

        // Stack এর বর্তমান অবস্থা
        System.out.println("Stack after push operations: " + stack);

        // Peek অপারেশন
        System.out.println("Top element using peek: " + stack.peek()); // 40

        // Pop অপারেশন
        System.out.println("Element popped: " + stack.pop()); // 40
        System.out.println("Stack after pop operation: " + stack);

        // আরও একটি pop অপারেশন
        System.out.println("Element popped: " + stack.pop()); // 30
        System.out.println("Stack after pop operation: " + stack);
    }
}

ব্যাখ্যা:

1. Push Operation: stack.push() মেথড ব্যবহার করে নতুন উপাদান স্ট্যাকে যোগ করা হয়। এখানে ১০, ২০, ৩০, এবং ৪০ এই মানগুলো স্ট্যাকে যোগ করা হয়েছে।
2. Peek Operation: stack.peek() মেথড ব্যবহার করে স্ট্যাকের শীর্ষ উপাদানটি দেখা যায়, কিন্তু এটি স্ট্যাক থেকে সরানো হয় না। এখানে, peek() ৪০ ফেরত দেবে কারণ এটি শীর্ষে রয়েছে।
3. Pop Operation: stack.pop() মেথড ব্যবহার করে শীর্ষ উপাদানটি সরানো হয় এবং তা রিটার্ন করা হয়। প্রথমে ৪০ সরানো হয় এবং তারপর ৩০ সরানো হয়।

আউটপুট:

Stack after push operations: [10, 20, 30, 40]
Top element using peek: 40
Element popped: 40
Stack after pop operation: [10, 20, 30]
Element popped: 30
Stack after pop operation: [10, 20]

৩. Stack Operations' Complexity

• Push: প্রতি push() অপারেশন O(1) সময়ে সম্পন্ন হয়। এর মানে, নতুন উপাদান স্ট্যাকে যোগ করতে সময় লাগবে না, যতটুকু জায়গা পাওয়া যায়।
• Pop: প্রতি pop() অপারেশন O(1) সময়ে সম্পন্ন হয়। এটি শীর্ষ উপাদানটি অপসারণ করে এবং সেই উপাদানকে রিটার্ন করে।
• Peek: প্রতি peek() অপারেশন O(1) সময়ে সম্পন্ন হয়। এটি শীর্ষ উপাদানটি শুধুমাত্র দেখতে দেয়, তবে সেটি অপসারিত হয় না।

৪. Stack এর ব্যবহার

Stack বিভিন্ন প্রোগ্রামিং পরিস্থিতিতে ব্যবহার করা হয়, যেমন:

1. Function Call Stack: যখন একটি ফাংশন কল করা হয়, তখন এটি একটি স্ট্যাক হিসেবে কাজ করে এবং প্রতিটি কল একটি নতুন ফ্রেম হিসাবে স্ট্যাকে প্রবেশ করে। ফাংশন শেষ হলে স্ট্যাক থেকে তা সরানো হয়।
2. Undo Operations: একটি অ্যাপ্লিকেশনে undo ফিচারের জন্য স্ট্যাক ব্যবহার করা হয়। ব্যবহারকারী শেষ যে কার্যক্রমটি করেছে, তা স্ট্যাকে প্রবেশ করে এবং undo করার জন্য স্ট্যাক থেকে অপসারিত হয়।
3. Expression Evaluation: স্ট্যাক গণনা এবং এক্সপ্রেশন প্রক্রিয়াকরণের জন্য ব্যবহার করা হয়, বিশেষ করে infix, prefix, এবং postfix এক্সপ্রেশন সমাধান করতে।
4. Depth First Search (DFS): গাছ বা গ্রাফের গহীর অনুসন্ধানের জন্য DFS অ্যালগরিদমে স্ট্যাক ব্যবহৃত হয়।

৫. Stack using Linked List (Custom Implementation)

যদিও Stack ক্লাস জাভাতে সহজেই ব্যবহৃত হয়, তবে আপনি যদি নিজস্ব স্ট্যাক ইমপ্লিমেন্টেশন করতে চান, তবে Linked List ব্যবহার করা যেতে পারে। এখানে একটি কাস্টম স্ট্যাক ইমপ্লিমেন্টেশন দেওয়া হল যা LinkedList ব্যবহার করে তৈরি করা হয়েছে:

class StackUsingLinkedList {
    private class Node {
        int data;
        Node next;
        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    private Node top;

    public StackUsingLinkedList() {
        top = null;
    }

    // Push operation
    public void push(int data) {
        Node newNode = new Node(data);
        newNode.next = top;
        top = newNode;
    }

    // Pop operation
    public int pop() {
        if (top == null) {
            System.out.println("Stack is empty!");
            return -1;
        }
        int popped = top.data;
        top = top.next;
        return popped;
    }

    // Peek operation
    public int peek() {
        if (top == null) {
            System.out.println("Stack is empty!");
            return -1;
        }
        return top.data;
    }

    public boolean isEmpty() {
        return top == null;
    }
}

public class CustomStackExample {
    public static void main(String[] args) {
        StackUsingLinkedList stack = new StackUsingLinkedList();

        stack.push(10);
        stack.push(20);
        stack.push(30);

        System.out.println("Top element: " + stack.peek());  // 30
        System.out.println("Popped element: " + stack.pop()); // 30
        System.out.println("Popped element: " + stack.pop()); // 20
    }
}

ব্যাখ্যা:

• Node Class: একটি Node ক্লাস তৈরি করা হয়েছে যা স্ট্যাকের প্রতিটি উপাদান ধারণ করবে এবং পরবর্তী নোডের সাথে সংযুক্ত থাকবে।
• Push: নতুন নোড তৈরি করা হয় এবং সেটি স্ট্যাকের শীর্ষে যুক্ত করা হয়।
• Pop: শীর্ষ নোড থেকে ডেটা নিয়ে তা সরানো হয়।
• Peek: শীর্ষ নোডের ডেটা দেখা হয়, কিন্তু সরানো হয় না।

সারাংশ

Stack হল একটি গুরুত্বপূর্ণ ডেটা স্ট্রাকচার যা LIFO (Last In First Out) পদ্ধতির মাধ্যমে কাজ করে। এর তিনটি মৌলিক অপারেশন হল Push, Pop, এবং Peek। জাভাতে Stack ক্লাস ব্যবহার করে সহজেই এই অপারেশনগুলি সম্পাদন করা যায়। তাছাড়া, আপনি যদি কাস্টম স্ট্যাক ইমপ্লিমেন্ট করতে চান, তবে Linked List ব্যবহার করে নিজে স্ট্যাক তৈরি করতে পারেন। স্ট্যাকের এই অপারেশনগুলি বিভিন্ন সমস্যা সমাধানে যেমন function calls, undo operations, DFS ইত্যাদিতে ব্যবহার করা হয়।